#include <iostream>
#include <map>
#include <vector>

using namespace std;

const int N = 210;

int eljut[N][N][6];
int eljut_temp[N][N][6];

void novel(int uj_i,int uj_j, int regi_i,int regi_j,int regi_k)
{
    if(0<=uj_i && uj_i<N && 0<=uj_j && uj_j<N)
    {
        eljut_temp[uj_i][uj_j][(regi_k+5)%6] = (eljut_temp[uj_i][uj_j][(regi_k+5)%6] + eljut[regi_i][regi_j][regi_k])%123456789;
        eljut_temp[uj_i][uj_j][(regi_k+1)%6] = (eljut_temp[uj_i][uj_j][(regi_k+1)%6] + eljut[regi_i][regi_j][regi_k])%123456789;
    }
}
int main()
{
    for(int i=0;i<N;++i)
        for(int j=0;j<N;++j)
            for(int k=0;k<6;++k)
                eljut[i][j][k]=0;

    eljut[N/2][N/2][0]=1;
    for(int c=0;c<200;++c)
    {
        for(int i=0;i<N;++i)
            for(int j=0;j<N;++j)
                for(int k=0;k<6;++k)
                    eljut_temp[i][j][k]=0;

        for(int i=0;i<N;++i)
            for(int j=0;j<N;++j)
                for(int k=0;k<6;++k)
                {
                    if(k==0) novel(i+1,j,i,j,k);
                    if(k==1) novel(i,j+1,i,j,k);
                    if(k==2) novel(i-1,j+1,i,j,k);
                    if(k==3) novel(i-1,j,i,j,k);
                    if(k==4) novel(i,j-1,i,j,k);
                    if(k==5) novel(i+1,j-1,i,j,k);
                }

        for(int i=0;i<N;++i)
            for(int j=0;j<N;++j)
                for(int k=0;k<6;++k)
                    eljut[i][j][k] = eljut_temp[i][j][k];

    }
    cout<<eljut[N/2][N/2][0];
}
